package com.hoppinzq.algorithm.linear;

import com.hoppinzq.algorithm.linear.interfs.MyList;

import java.util.Iterator;

/**
 * 可扩容的线性表之顺序存储结构
 * 线性表底层是数组
 * 初始化的时候会占用今可能大的空间（因为顺序表的存储空间是连续的），所以空间复杂度高，整体空间利用率低。但单个存储单元的空间利用率比链表高，存储密度大。
 * 在查找或修改时执行效率高，时间复杂度是O(1)
 * 在添加或删除时执行效率低，时间复杂度是O(n)，尤其体现在起始位置进行添加或者删除操作。且扩容不方便，需要额外开辟一块新内存，开销比较大。
 * 能随机存取
 * @param <T>
 */
public class MyArrayList<T> implements MyList<T>,Iterable<T>{

    //存储的数据
    private T[] elementData;
    //长度
    private int N;

    /**
     * 构造方法
     * @param length
     */
    public MyArrayList(int length){
        //初始化长度
        elementData=(T[])new Object[length];
        N=0;
    }

    /**
     * 清空线性表
     */
    @Override
    public void clear() {
        N=0;
    }

    /**
     * 判空
     * @return
     */
    @Override
    public boolean isEmpty() {
        return N==0;
    }

    /**
     * 返回线性表长度
     * @return
     */
    @Override
    public int length() {
        return N;
    }

    /**
     * 根据索引查询内容
     * 时间复杂度 O(1)
     * @param i
     * @return
     */
    @Override
    public T get(int i) {
        return elementData[i];
    }

    /**
     * 插入数据
     * @param o
     */
    @Override
    public void insert(T o) {
        if(elementData.length==N){
            resize(2*N);
        }
        elementData[N++]=o;
    }

    /**
     * 扩容/缩容
     * @param length
     */
    private void resize(int length){
        T[] temp=elementData;
        elementData=(T[])new Object[length];
        for(int i=0;i<N;i++){
            elementData[i]=temp[i];
        }
    }

    /**
     * 指定索引插入数据
     * 时间复杂度 O(n) ，并且有不可预知的扩容的开销
     * @param i
     * @param o
     */
    @Override
    public void insert(int i, T o) {
        if(elementData.length==N){
            resize(2*N);
        }
        for(int index=N-1;index>=i;index--){
            elementData[index+1]=elementData[index];
        }
        elementData[i]=o;
        N++;
    }

    /**
     * 删除指定索引的内容
     * @param i
     * @return
     */
    @Override
    public T remove(int i) {
        T temp=elementData[i];
        for(int index=i;index<N;index++){
            elementData[index]=elementData[index+1];
        }
        N--;
        if(elementData.length<=N/4){
            resize(N/2);
        }
        return temp;
    }

    /**
     * 返回第一次出现指定数据的索引，没有返回-1
     * @param o
     * @return
     */
    @Override
    public int indexOf(T o) {
        for(int i=0;i<N;i++){
            if(elementData[i].equals(o)){
                return i;
            }
        }
        return -1;
    }

    /**
     * 迭代器
     * 添加遍历功能，方便打印测试
     * @return
     */
    @Override
    public Iterator<T> iterator() {
        return new AIterator();
    }

    private class AIterator implements Iterator{
        private int cusor;
        public AIterator(){
            this.cusor=0;
        }
        @Override
        public boolean hasNext() {
            return cusor<N;
        }

        @Override
        public Object next() {
            return elementData[cusor++];
        }
    }
}
